package com.acwing.partition22;

import java.io.*;
import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2022/4/24 15:29
 */
public class AC2193分配问题 {

    private static final int N = 55, INF = 0x3f3f3f3f;
    private static int[][] g = new int[N][N];
    private static int[] la = new int[N], lb = new int[N], match = new int[N], upd = new int[N];
    private static boolean[] va = new boolean[N], vb = new boolean[N];
    private static int n;

    private static StreamTokenizer tokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    private static PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        n = nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                g[i][j] = nextInt();
            }
        }
        //最小总收益
        writer.println(km(0));
        for (int i = 1; i <= n; i++) {
            la[i] = lb[i] = match[i] = upd[i] = 0;
            va[i] = vb[i] = false;
        }
        //最大总收益
        writer.println(km(1));
        writer.flush();
    }

    private static int km(int op) {
        //初始化左部点的顶标为所有与右部点相连边权的最大值；右部点的顶标初始都为0
        for (int l = 1; l <= n; l++) {
            la[l] = g[l][1];
            for (int r = 2; r <= n; r++) {
                if (op == 1) la[l] = Math.max(la[l], g[l][r]);
                else la[l] = Math.min(la[l], g[l][r]);
            }
        }
        //尝试为每一个左部点匹配
        for (int l = 1; l <= n; l++) {
            if (op == 1) Arrays.fill(upd, INF);
            else Arrays.fill(upd, -INF);
            while (true) {
                for (int i = 0; i < N; i++) va[i] = vb[i] = false;
                //如果能够给当前左部点找到一个匹配点，就退出；如果找不到，就降低涉及到的左部点的期望
                if (dfs(l, op)) break;
                int t = op == 1 ? INF : -INF;
                for (int r = 1; r <= n; r++) {
                    if (!vb[r] && op == 1) t = Math.min(t, upd[r]);
                    if (!vb[r] && op != 1) t = Math.max(t, upd[r]);
                }
                //所有涉及到的左部点降低期望，右部点增加
                for (int i = 1; i <= n; i++) {
                    if (va[i]) la[i] -= t;
                    if (vb[i]) lb[i] += t;
                    else upd[i] -= t;
                }
            }
        }
        int res = 0;
        for (int r = 1; r <= n; r++) res += g[match[r]][r];
        return res;
    }

    private static boolean dfs(int l, int op) {
        va[l] = true;
        for (int r = 1; r <= n; r++) {
            //每一轮匹配，右部点只参与一次
            if (vb[r]) continue;
            int t = la[l] + lb[r] - g[l][r];
            if (t == 0) {
                vb[r] = true;
                //如果右部点没有被匹配或者能够给这个节点对应的左部点找一个匹配点，就给当前l匹配上r
                if (match[r] == 0 || dfs(match[r], op)) {
                    match[r] = l;
                    return true;
                }
            } else {
                if (op == 1) upd[r] = Math.min(upd[r], t);
                else upd[r] = Math.max(upd[r], t);
            }
        }
        return false;
    }

    private static int nextInt() throws IOException {
        tokenizer.nextToken();
        return (int) tokenizer.nval;
    }
}
